//
// Created by LiuYou on 2021/11/28.
//

#include <iostream>
#include <vector>
#include <iterator>


static void swap(int arr[], int x, int y) {
    if (x != y) {
        arr[x] = arr[x] ^ arr[y];
        arr[y] = arr[x] ^ arr[y];
        arr[x] = arr[x] ^ arr[y];
    }
}


/**
 * @brief 插入排序。
 * @param arr 要排序的数组。
 *
 * @details 为什么说插入排序要比选择排序和冒泡排序好一点呢?
 * 因为不同的数据状况, 插入排序会表现的更好一些。
 * 选择排序和冒泡排序是严格的O(n2), 而插入排序某些情况下, 不是严格的O(n2)。
 * <strong>所以插入排序是要优于选择排序和冒泡排序的。</strong>
 *
 *
 */
static void insertionSort(std::vector<int>& arr) {
    if (arr.empty() || arr.size() < 2) {
        return;
    }

    // 0 ~ 0 是有序的。0 ~ 0 就一个数, 就是有序的。
    // 0 ~ i 想有序。
    //
    // 第一个for循环: 我要每一步完成的目标 -> 我想要在 0 ~ 1 范围内有序;
    // 想要在 0 ~ 2 范围内有序; 想要在 0 ~ 3 范围内有序; ...; 最后我想在
    // 0 ~ n-1 范围上有序。
    for (int i = 1; i < arr.size(); ++i) {
        // j >= 0 表示 j 不越界。
        for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; --j) {
//            std::swap( arr[j], arr[j + 1] );
            swap( arr.data(), j, j + 1 );
        }
    }
}


int main(int argc, char** argv) {
    std::vector<int> arr{33, 11, 325, 0, 4, 96, 6, 7, 4};

    {
        insertionSort( arr );
        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, " " ));
        std::cout << std::endl;
    }


    return 0;
}
